package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/split-linked-list-in-parts">分隔链表(Split Linked List in Parts)</a>
 * <p>给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。</p>
 * <p>每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。</p>
 * <p>这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。</p>
 * <p>返回一个由上述 k 部分组成的数组。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3], k = 5
 *      输出：[[1],[2],[3],[],[]]
 *      解释：
 *          第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
 *          最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。
 *
 * 示例 2：
 *      输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
 *      输出：[[1,2,3,4],[5,6,7],[8,9,10]]
 *      解释：
 *          输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>链表中节点的数目在范围 [0, 1000]</li>
 * <li>0 <= Node.val <= 1000</li>
 * <li>1 <= k <= 50</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/4 17:46
 */
public class LC0725SplitLinkedListInParts_M {
    static class Solution {
        public ListNode[] splitListToParts(ListNode head, int k) {
            // 计算链表的长度
            int length = 0;
            ListNode currNode = head;
            while (currNode != null) {
                ++length;
                currNode = currNode.next;
            }
            // 计算分割成 k 个部分后，每个部分的平均节点个数
            int n = length / k;
            // k 个部分，每个部分 n 个节点，剩余的节点个数
            int r = length % k;
            ListNode[] res = new ListNode[k];
            currNode = head;
            for (int i = 0; i < k && currNode != null; i++) {
                res[i] = currNode;
                // 将剩余的 remainder 个节点，分配到前 remainder 个链表中。
                int size = n + (i < r ? 1 : 0);
                // 注意需要从1开始
                for (int j = 1; j < size; j++) {
                    currNode = currNode.next;
                }
                // 此时恰好到每一段链表的尾部，记录下一段链表的头节点
                ListNode nextNode = currNode.next;
                // 将当前链表与下一段链表断开
                currNode.next = null;
                // 进入下一段链表
                currNode = nextNode;
            }
            return res;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);
        head2.next.next.next.next.next = new ListNode(6);
        head2.next.next.next.next.next.next = new ListNode(7);
        head2.next.next.next.next.next.next.next = new ListNode(8);
        head2.next.next.next.next.next.next.next.next = new ListNode(9);
        head2.next.next.next.next.next.next.next.next.next = new ListNode(10);

        Solution solution = new Solution();
        ListNode[] listNodes1 = solution.splitListToParts(head1, 5);
        for (ListNode listNode : listNodes1) {
            Printer.printListNode(listNode);
        }
        System.out.println("============");

        ListNode[] listNodes2 = solution.splitListToParts(head2, 3);
        for (ListNode listNode : listNodes2) {
            Printer.printListNode(listNode);
        }
    }
}